using System;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
using CellType = System.Int32;

public class Distance
{
    const int MTC = 2;
    const int sizelimit = 20000;
    public Distance(){}
    static int level;
    static List<int>[] groups;
    static int[] gids, levels, us, vs;
    static int index;
    static string[] g;
    static int n, m = sizelimit;
    static Dictionary<Pair, int> set;
    static List<int>[] adjList, adjList1, adjs;
    static DateTime startTime;
    static int linkCount, mlinkCount, oGrouping;
    static Distance[] ds;
    static double[] queryret;
    static Thread[] ts;

    public double[] query(int[] u, int[] v)
    {
        us = u;
        vs = v;
        DateTime startTime = DateTime.Now;
        queryret = new double[u.Length];
        index = -1;
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i].Start();
        }
        ds[MTC - 1].q();
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i].Join();
        }

        Console.WriteLine("{0}\tQuery", DateTime.Now - startTime);
        return queryret;
    }
    public int process(string[] graphs)
    {
        linkCount = 0;
        mlinkCount = 0;
        oGrouping = 0;
        startTime = DateTime.Now;
        n = graphs.Length;
        ts = new Thread[MTC-1];
        ds = new Distance[MTC];
        for (int i = 0; i < MTC; i++)
        {
            ds[i] = new Distance(i);
        }
        g = graphs;
        //vs = new float[n];

//begin
        Console.WriteLine("{0}\tbegin", DateTime.Now - startTime);
        gids = new int[n];
        levels = new int[n];
        adjList = new List<int>[n];
        adjList1 = new List<int>[n];

//init
        Console.WriteLine("{0}\tinit...", DateTime.Now - startTime);
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i] = new Thread(new ThreadStart(ds[i].init));
            ts[i].Start();
        }
        ds[MTC - 1].init();
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i].Join();
        }

//init g
        Console.WriteLine("{0}\tinit g...      ", DateTime.Now - startTime);
        index = -1;
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i] = new Thread(new ThreadStart(ds[i].initg));
            ts[i].Start();
        }
        ds[MTC - 1].initg();
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i].Join();
        }

        //tidy
        //Console.WriteLine("{0}\ttidy...", DateTime.Now - startTime);
        //for (int i = MTC - 2; i >= 0; i--)
        //{
        //    ts[i] = new Thread(new ThreadStart(ds[i].tidy));
        //    ts[i].Start();
        //}
        //ds[MTC - 1].tidy();
        //for (int i = MTC - 2; i >= 0; i--)
        //{
        //    ts[i].Join();
        //}
        //Console.WriteLine("{0}\tlinkCount", linkCount);

//grouping
        Console.WriteLine("{0}\tgrouping...", DateTime.Now - startTime);
        for (level = 1; m >= sizelimit; level++)
        {
            Console.WriteLine("{0}\t[{1}]level...", DateTime.Now - startTime, level);
            //for (int i = n - 2; i >= 0; i--)
            //{
            //    nodes[i].next = nodes[i + 1];
            //}
            for (int i = 0; i < n; i++)
            {
                gids[i] = -1;
                levels[i] = int.MaxValue;
            }

            m = -1;
            index = -1;
            for (int i = MTC - 2; i >= 0; i--)
            {
                ts[i] = new Thread(new ThreadStart(ds[i].grouping));
                ts[i].Start();
            }
            ds[MTC - 1].grouping();
            for (int i = MTC - 2; i >= 0; i--)
            {
                ts[i].Join();
            }

            Console.WriteLine("{0}\t[{1}]level done", DateTime.Now - startTime, level);
        }
        m++;
        //Thread threadInitMap = new Thread(new ThreadStart(initMap));
        //threadInitMap.Priority = ThreadPriority.BelowNormal;
        //threadInitMap.Start();
        level++;
        Console.WriteLine("{0}\toGrouping", oGrouping);


        groups = new List<int>[m];
        for (int i = 0; i < m; i++)
        {
            groups[i] = new List<int>();
        }
        for (int i = 0; i < n; i++)
        {
            groups[gids[i]].Add(i);
        }

//internal distances
        //Console.WriteLine("{0}\tinternal distances...", DateTime.Now - startTime);
        //int[,] ls = new int[m, level];
        //int[] gs = new int[m];
        //for (int i = 0; i < n; i++)
        //{
        //    ls[gids[i], levels[i]]++;
        //    gs[gids[i]]++;
        //}
        //int maxGroupSize = 0;
        //for(int i=0; i<m; i++)
        //{
        //    if(maxGroupSize<gs[i])
        //    {
        //        maxGroupSize = gs[i];
        //    }
        //}
        //Console.WriteLine("{0}\tmax gs", maxGroupSize);
        //Console.WriteLine("{0}\tm", m);
        //gl = new float[m];
        //double maxInternalDistance = 0;
        //for (int i = 0; i < m; i++)
        //{
        //    int a = 0, b = 0, c = 0;
        //    for (int j = 0; j < level; j++)
        //    {
        //        c += ls[i, j];
        //        a += ls[i, j] * j;
        //        b += ls[i, j] * (a - (j-1-c) * j);
        //    }
        //    gl[i] = (float)((double)b / (double)(c*c));
        //    if(maxInternalDistance<gl[i])
        //    {
        //        maxInternalDistance = gl[i];
        //    }
        //}
        //Console.WriteLine("{0}\tmaxInternalDistance", maxInternalDistance);
        //for (int i = 0; i < n; i++)
        //{
        //    vs[i] = gl[gids[i]];
        //}

//adjs
        Console.WriteLine("{0}\tadjs...", DateTime.Now - startTime);
        index = -1;
        adjs = new List<int>[m];
        set = new Dictionary<Pair, int>(m);
        for (int i = 0; i < m; i++)
        {
            adjs[i] = new List<int>();
        }

        //threadInitMap.Join();
        Console.WriteLine("{0}\tadjs join...", DateTime.Now - startTime);
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i] = new Thread(new ThreadStart(ds[i].adj));
            ts[i].Start();
        }
        ds[MTC - 1].adj();
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i].Join();
        }
        Console.WriteLine("{0}\tmlinkCount", mlinkCount);

////external distances
//        Console.WriteLine("{0}\texternal distances...", DateTime.Now - startTime);
//        index = -1;
//        for (int i = 0; i < MTC-1; i++)
//        {
//            ts[i] = new Thread(new ThreadStart(ds[i].run));
//            ts[i].Start();
//        }
//        ds[MTC - 1].run();
//        for (int i = 0; i < MTC - 1; i++)
//        {
//            ts[i].Join();
//        }
//        Console.WriteLine("{0}\tdone...", DateTime.Now - startTime);

        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i] = new Thread(new ThreadStart(ds[i].q));
        }

        return 0;
    }

    private Distance(int id)
    {
        table = new short[n];
        mtable = new int[m];
        this.id = id;
        start = id * n / MTC;
        end = (id + 1) * n / MTC;
    }

    private int id, start, end;
    private void init()
    {
        for (int i = start; i < end; i++)
        {
            adjList[i] = new List<int>(50);
            adjList1[i] = new List<int>(20);
        }
    }
    private void initg()
    {
        int i;
        while ((i = Interlocked.Increment(ref index)) < n)
        //for (int i = start; i < end; i++)
        {
            List<int> list = adjList[i], list1;
            foreach (string s in g[i].Split(' '))
            {
                int a = int.Parse(s);
                if(a != i)
                {
                    lock (list)
                    {
                        list.Add(a);
                    }
                    list1 = adjList[a];
                    lock (list1)
                    {
                        list1.Add(i);
                    }
                    adjList1[i].Add(a);
                }
            }
        }
    }
    private void tidy()
    {
        int start = id * n / MTC, end = (id + 1) * n / MTC;
        Dictionary<int, int> set = new Dictionary<int, int>(40);
        List<int> newList = new List<int>(20), tmp;
        for (int i = start; i < end; i++)
        {
            set.Clear();
            newList.Clear();
            bool dif = false;
            foreach (int a in adjList[i])
            {
                if (!set.ContainsKey(a))
                {
                    Interlocked.Increment(ref linkCount);
                    set.Add(a, 0);
                    newList.Add(a);
                }
                else
                {
                    dif = true;
                }
            }
            if (dif)
            {
                tmp = adjList[i];
                adjList[i] = newList;
                newList = tmp;
            }
        }
    }
    private void adj()
    {
        int i;
        while ((i = Interlocked.Increment(ref index)) < n)
        //for (int i = start; i < end; i++)
        {
            int ga = gids[i];
            foreach (int j in adjList1[i])
            {
                int gb = gids[j];
                if (ga != gb)
                {
                    lock (set)
                    {
                        if(!set.ContainsKey(new Pair(ga, gb)))
                        {
                            set.Add(new Pair(ga, gb), 0);
                            set.Add(new Pair(gb, ga), 0);
                            adjs[ga].Add(gb);
                            adjs[gb].Add(ga);
                        }
                    }
                }
            }
        }
    }
    //private void run()
    //{
    //    List<int> q1 = new List<int>(), q2 = new List<int>(), q3;
    //    int i;
    //    while ((i = Interlocked.Increment(ref index)) < m)
    //    {
    //        q1.Clear();
    //        CellType v = 0;
    //        q1.Add(i);
    //        map[i, i] = CellType.MaxValue;
    //        do
    //        {
    //            v++;
    //            q2.Clear();
    //            foreach (int a in q1)
    //            {
    //                //float d = map[i, a]+1;
    //                foreach (int b in adjs[a])
    //                {
    //                    if (map[i, b] <= 0)// || map[i,b]>d+gl[b])
    //                    {
    //                        q2.Add(b);
    //                        map[i, b] = v;// d + gl[b];
    //                    }
    //                }
    //            }
    //            q3 = q2;
    //            q2 = q1;
    //            q1 = q3;
    //        }
    //        while (q1.Count > 0);
    //        map[i, i] = 0;
    //    }
    //}

    private void q()
    {
        int i;
        while((i = Interlocked.Increment(ref index))<queryret.Length)
        {
            queryret[i] = this.distance(us[i], vs[i], i);
        }
    }
    short[] table;
    int[] mtable;
    List<int> q1 = new List<int>(), q2 = new List<int>(), q3 = new List<int>(), qg = new List<int>();
    private double distance(int U, int V,int index)
    {
        if (U == V)
            return 0;
        double ret = 0;
        List<int> qt;
        Array.Clear(mtable, 0, m);
        int u = gids[U], v = gids[V];
        short mark = (short)(-index - 1);
        qg.Clear();
        qg.Add(u);
        if (u != v)
        {
            qg.Add(v);
            q1.Clear();
            q2.Clear();
            q1.Add(u);
            q2.Add(v);
            mtable[u] = u + 1;
            mtable[v] = -v - 1;
            int t;
            for (; q1.Count>0; )
            {
                ret++;
                q3.Clear();
                foreach (int a in q1)
                {
                    foreach (int aa in adjs[a])
                    {
                        if (mtable[aa] == 0)
                        {
                            mtable[aa] = a + 1;
                            q3.Add(aa);
                        }
                        else if(mtable[aa] < 0)
                        {
                            for (t = aa; t != v; t = -1 - mtable[t])
                            {
                                qg.Add(t);
                            }
                            for (t = a; t != u; t = mtable[t] - 1)
                            {
                                qg.Add(t);
                            }
                            goto MDone;
                        }
                    }
                }
                qt = q3;
                q3 = q1;
                q1 = qt;

                ret++;
                q3.Clear();
                foreach (int a in q2)
                {
                    foreach (int aa in adjs[a])
                    {
                        if (mtable[aa] == 0)
                        {
                            mtable[aa] = -a - 1;
                            q3.Add(aa);
                        }
                        else if (mtable[aa] > 0)
                        {
                            for (t = a; t != v; t = -1 - mtable[t])
                            {
                                qg.Add(t);
                            }
                            for (t = aa; t != u; t = mtable[t] - 1)
                            {
                                qg.Add(t);
                            }
                            goto MDone;
                        }
                    }
                }
                qt = q3;
                q3 = q2;
                q2 = qt;
            }
            throw new Exception();
        }
    MDone:
        int c=0;
        foreach(int i in qg)
        {
            c += groups[i].Count;
            foreach(int a in groups[i])
            {
                table[a] = mark;
            }
        }
        //Console.WriteLine("{0} c", c);
        //for(int i=0; i<n; i++)
        //{
        //    table[i] = mark;
        //}
        int ul = 0, vl = 0;
        short mark1 = (short)((index+1)*2), mark2 = mark1;
        mark2++;
        q1.Clear();
        q2.Clear();
        qg.Clear();
        q1.Add(U);
        q2.Add(V);
        table[U] = 2;
        table[V] = 1;
        qg.Add(U);
        qg.Add(V);
        for(;q1.Count>0;)
        {
            ul++;
            q3.Clear();
            foreach(int a in q1)
            {
                foreach(int aa in adjList[a])
                {
                    if(table[aa] == mark)
                    {
                        q3.Add(aa);
                        table[aa] = mark2;
                    }
                    else if (table[aa] == mark1)
                    {
                        return (ret + ul + vl)/2;
                    }
                }
            }
            qt = q1;
            q1 = q3;
            q3 = qt;

            vl++;
            q3.Clear();
            foreach(int a in q2)
            {
                foreach(int aa in adjList[a])
                {
                    if(table[aa] == mark)
                    {
                        q3.Add(aa);
                        table[aa] = mark1;
                    }
                    else if (table[aa] == mark2)
                    {
                        return (ret + ul + vl) / 2;
                    }
                }
            }
            qt = q2;
            q2 = q3;
            q3 = qt;
        }
        return -1;

    }
    private void grouping()
    {
        List<int> queue1 = new List<int>();
        List<int> queue2 = new List<int>();
        Dictionary<int, int> set = new Dictionary<int, int>();
        int i;
    NextLoop:
        while((i = Interlocked.Increment(ref index))<n)
        {
            if (gids[i] < 0)
            {
                int gid = Interlocked.Increment(ref m);
                if (gid >= sizelimit)
                    break;
                queue1.Clear();
                queue2.Clear();
                set.Clear();
                queue1.Add(i);
                set.Add(i, 0);
                for (int j = 0; queue1.Count > 0 && j < level; j++)
                {
                    foreach (int a in queue1)
                    {
                        lock (adjList[a])
                        {
                            if (levels[a] > j)
                            {
                                gids[a] = gid;
                                levels[a] = j;
                            }
                        }
                        if (gids[a] == gid)
                        {
                            foreach (int b in adjList[a])
                            {
                                if (!set.ContainsKey(b) && levels[b] > j)
                                {
                                    queue2.Add(b);
                                    set.Add(b, 0);
                                }
                            }
                        }
                    }
                    queue1.Clear();
                    List<int> tmp = queue1;
                    queue1 = queue2;
                    queue2 = tmp;
                }
                if (queue1.Count > 0)
                {
                    foreach (int a in queue1)
                    {
                        lock (adjList[a])
                        {
                            if (levels[a] > level)
                            {
                                gids[a] = gid;
                                levels[a] = level;
                            }
                        }
                    }
                }
            }
        }
    }

}

public struct Pair
{
    public Pair(int a, int b)
    {
        this.a = a;
        this.b = b;
    }
    public int a, b;
    public override int GetHashCode()
    {
        return a ^ b;
    }
};
